1. Field of the Invention
The present invention relates to a method of and an apparatus for determining adjoining relationships between a plurality of image parts. The present invention also relates to a method of and an apparatus for processing image data which include parts data representing a plurality of image parts that are drawn in a predefined drawing order while determining adjoining relationships between the plurality of image parts.
2. Description of the Related Art
In the field of prepress processing, one image generally consists of a plurality of image parts. When two image parts are located adjacent to each other, an overlapping area (also referred to as xe2x80x98trapping areaxe2x80x99 or an xe2x80x98overlaying areaxe2x80x99) is formed on a boundary between the adjoining image parts, in order to prevent a dropout from being observed on the boundary.
In order to generate a trapping area, it is required first to determine which pair of image parts among the plurality of image parts adjoin to each other. The expression xe2x80x98image parts adjoining to each otherxe2x80x99 means that the image parts are in close contact with each other without any clearance on at least part of the boundary between the image parts, or they overlap each other at least partially.
FIGS. 13A-13C show a known method of determining adjoining relationships between a plurality of image parts. In the conventional process of determining an adjoining relationship between two image parts shown in FIG. 13A, it is first determined whether the circumscribed rectangles of the respective image parts shown by the broken lines in FIG. 13B overlap each other. When the circumscribed rectangles overlap each other, the two image parts may adjoin to each other. It is then determined whether vectors representing the contours of the respective image parts cross each other as shown in FIG. 13C. When the contour vectors cross each other or partially overlap each other, the two image parts are determined to adjoin to each other. It is here assumed that one general image consists of N image parts and that the contour of each image part consists of xe2x80x98nxe2x80x99 vectors. The processing time required for determining the overlapping relationships between the respective pairs of circumscribed rectangles of the N image parts is in proportion to the number N of the image parts. The processing time required for determining whether the contour vectors of the two image parts cross each other is in proportion to the second power of the number xe2x80x98nxe2x80x99 of the contour vectors. Namely the total processing time required for extracting all the possible combinations of two image parts from the N image parts and determining whether the contour vectors cross each other for all the possible combinations is expected to be substantially in proportion to n2xc3x97N2.
In the conventional method discussed above, as the number N of the image parts or the number n of the vectors constituting the contour vector of each image part increases, the required processing time remarkably increases in proportion to the second power of the increased number. An extremely long time is required for the processing especially when the number N of image parts is as large as tens or hundreds of thousands.
Incidentally, in DTP (desktop publishing) applications using a computer system, a group of consecutive figures having a fixed rate of density variation sometimes creates an image area having a substantially continuous gradation in density. This group of consecutive figures is generally referred to as a xe2x80x98blendxe2x80x99, xe2x80x98blend figurexe2x80x99 or xe2x80x98color stepxe2x80x99. Although each figure included in the blend figure represents one individual figure, the group of figures is drawn to generate an image area having a substantially continuous change in density.
In some cases, it is necessary to form a trapping area on a boundary between a blend figure and another image part. Image data (for example, a page description language such as PostScript (trademark of Adobe Corporation)), however, do not include information indicating that the image part is part of the blend figure. In the conventional method, the trapping process is accordingly carried out between each image part included in the blend figure and another image part not included in the blend figure. This undesirably increases the processing time required for creating a trapping area. This problem is not characteristic of the trapping process but is found in a variety of image processing operations with respect to the blend figure.
An object of the present invention is thus to provide an improved technique which alleviate the increase in required processing time even when the number of image parts increases remarkably.
Another object of the present invention is thus to provide an improved technique which carries out a desired image processing without processing the respective image parts included in a blend figure separately.
The above objects are at least partially attained by a method of determining adjoining relationships between a plurality of image parts according to the present invention. The method comprises the steps of: (a) generating bit map images by allocating different pixel values to the plurality of image parts, and filling the inside of the contour of each the image part with the allocated pixel value; and (b) examining pixel values of neighboring pixels in the bit map images, and recognizing adjoining relationship between image parts including the neighboring pixels when the neighboring pixels have different pixel values.
According to the above method, only the processing time for bit-mapping increases as the number of image parts increases. Therefore the increase of the overall processing time is much smaller than that of the conventional method even when the number of image parts increases remarkably.
In a preferred embodiment, the pixel values are drawing orders of the plurality of image parts. In another embodiment, the method further comprises the step of: specifying resolution of the bit map images before the step (a); and wherein the generating in the step (a) generates the bit map images with the resolution.
According to an aspect of the preset invention, the step (a) comprises the step of successively writing the bit map images into one bit map memory in a drawing order of the plurality of image parts; and the step (b) comprises the step of examining pixel values of neighboring pixels in the bit map images written in the bit map memory.
According to another aspect of the present invention, the method comprises the steps of: (a) recognizing consecutive image parts in the drawing order in the plurality of image parts to constitute one combined image part when each pair of image parts among the consecutive image parts adjoins to each other and a difference in density between the pair is smaller than a predetermined threshold value; and (b) carrying out a specific image processing for the combined image part.
This method enables a desired image processing to be carried out without separately processing the respective image parts which have been formed to constitute one combined image part.
In a preferred embodiment, the step (b) comprises the steps of: creating a trapping area, in which a density value of the combined image part being combined with a density value of another image part adjoining to the combined image part, on a boundary between the combined image part and the another image part; and generating a trapping area part by determining a density value of the trapping area based on a relationship between density values of the consecutive image parts constituting the combined image part and the density value of the another image part.
In another embodiment, the step (a) comprises the steps of: (1) generating bit map images by allocating different pixel values to the plurality of image parts and by filling the inside of a contour of each the image part with the allocated pixel value, and writing the bit map images in a bit map memory; (2) examining whether neighboring pixels in the bit map images have different pixel values or not; and (3) recognizing adjoining relationship between image parts including the neighboring pixels when the neighboring pixels have different pixel values.
This method enables a trapping area to be created on the boundary between the combined image part and another image part with a relatively short processing time.
The present invention is also directed to an apparatus for determining adjoining relationships between a plurality of image parts. The apparatus comprises: bit-mapping means for generating bit map images by allocating different pixel values to the plurality of image parts, and filling the inside of the contour of each the image part with the allocated pixel value; and recognizing means for examining pixel values of neighboring pixels in the bit map images, and recognizing adjoining relationship between image parts including the neighboring pixels when the neighboring pixels have different pixel values.
According to an aspect of the present invention, the apparatus comprises: recognizing means for recognizing consecutive image parts in the drawing order in the plurality of image parts to constitute one combined image part when each pair of image parts among the consecutive image parts adjoins to each other and a difference in density between the pair is smaller than a predetermined threshold value; and processing means for carrying out a specific image processing for the combined image part.
The present invention is further directed to a computer readable medium having computer readable program code means embodied therein for determining adjoining relationships between a plurality of image parts. The computer program code means comprises: computer program code means for causing a computer to generate bit map images by allocating different pixel values to the plurality of image parts, and to fill the inside of the contour of each the image part with the allocated pixel value; and computer program code means for causing the computer to examine pixel values of neighboring pixels in the bit map images, and to recognize adjoining relationship between image parts including the neighboring pixels when the neighboring pixels have different pixel values.
According to another aspect of the present invention, the computer program code means comprises: computer program code means for causing a computer to recognize consecutive image parts in the drawing order in the plurality of image parts to constitute one combined image part when each pair of image parts among the consecutive image parts adjoins to each other and a difference in density between the pair is smaller than a predetermined threshold value; and computer program code means for causing the computer to carry out a specific image processing for the combined image part.
These and other objects, features, aspects, and advantages of the present invention will become more apparent from the following detailed description of the preferred embodiments with the accompanying drawings.